package com.lzh.others.leetcode;

/**
 * 利用前缀提高效率
 * 还是不狗快
 */
public class LeetCode1371_01 {

    /**
     * int[i][k]表示字符串前 i 个字符中，第 k 个元音出现的次数
     */
    static int[][] pre;

    /**
     * 无匹配标记
     */
    static boolean flag = false;

    static final char A = 'a';
    static final char E = 'e';
    static final char I = 'i';
    static final char O = 'o';
    static final char U = 'u';

    public static int[][] initPre(String s) {
        int length = s.length();
        int[][] pre = new int[length][5];
        int countA = 0;
        int countE = 0;
        int countI = 0;
        int countO = 0;
        int countU = 0;
        for (int i = 0; i < length; i++) {
            char temp = s.charAt(i);
            if (temp == A) {
                countA++;
            }
            if (temp == E) {
                countE++;
            }
            if (temp == I) {
                countI++;
            }
            if (temp == O) {
                countO++;
            }
            if (temp == U) {
                countU++;
            }
            pre[i][0] = countA;
            pre[i][1] = countE;
            pre[i][2] = countI;
            pre[i][3] = countO;
            pre[i][4] = countU;
        }
        return pre;
    }

    /**
     * 判断字符串中元音字母出现的次数是否都是偶数
     *
     * @param start 子串开始索引
     * @param end   子串结束索引
     * @return true偶数;false奇数
     */
    public static boolean allAreEvenNum(int start, int end) {
        //前缀为0时
        if (start == 0) {
            for (int i = 0; i < 5; i++) {
                int nums = pre[end][i];
                if (nums % 2 != 0) {
                    return false;
                }
            }
            return true;
        }
        for (int i = 0; i < 5; i++) {
            int nums = pre[end][i] - pre[start - 1][i];
            if (nums % 2 != 0) {
                return false;
            }
        }
        return true;
    }

    public static int findTheLongestSubstring(String s) {
        int result = 0;
        int length = s.length();
        pre = initPre(s);
        for (int i = 0; i < length; i++) {
            int count = 1;
            for (int j = i + 1; j < length; j++) {
                count++;
                if (allAreEvenNum(i, j)) {
                    result = Math.max(count, result);
                }
            }
            char charAt = s.charAt(i);
            if (i + 1 == length
                    && result == 0
                    && (charAt != A && charAt != E && charAt != I && charAt != O && charAt != U)) {
                result = 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        long l = System.currentTimeMillis();
//                int nums = findTheLongestSubstring(s.toString());
//        System.out.println("result = " + nums);
//        System.out.println("cost = " + (System.currentTimeMillis() - l) + "ms");
    }

}
